package 动态规划.状态压缩dp;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/22 21:31
 */
public class leetcode292NimGame {

    // 超时
    public static boolean recursion(int n){
        if(n <= 3)
            return true;
        for(int i = 1;i <= 3;i++){
            if(!recursion(n - i))
                return true;
        }
        return false;
    }
    // 爆内存
    public boolean canWinNim(int n) {
        int dp [] = new int[n + 1];
        return recursion(n,dp);
    }
    public boolean recursion(int n,int dp[]){
        if(n <= 3)
            return true;
        if(dp[n] != 0)
            return dp[n] == 1 ? true :false;
        boolean ans = false;
        for(int i = 1;i <= 3;i++){
            if(!recursion(n - i,dp)){
                ans = true;
                /*
                如果不做记忆化搜索的话，这里写 return true 也是正确的
                但是  做 记忆化 ，就必须 把当前层的 递归给 标记 为 做过搜过了
                但是 直接return true 的话 就不会执行后面的代码了，
                这样的话 就 无法 标记 当前层的 递归  是 已经搜过的 了！
                这些小小的细节要明白
                 */
                break;
            }
        }
        dp[n] = ans ? 1 : -1;
        return ans;
    }

    public boolean canWinNimFinal(int n) {
        // n % 3 等价于 n % 4
        // n & 2 ^ N - 1 equals n % 2 ^ N
        return (n & 3) != 0;
    }

    /*
    整到最后却是个 找规律题
    也就是    ** 打表 **
    打表就出来了
     */
    public static void main(String[] args) {
        for(int i = 1;i <= 100;i++)
            System.out.println(i + " " + recursion(i));
    }

}
